package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.LeetCode;

@LeetCode
public class Knapsack {

    // A utility function that returns maximum of two integers
    static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSack(int totalWeight, int weight[], int value[], int n) {
        // Base Case
        if (n == 0 || totalWeight == 0)
            return 0;

        // If weight of the nth item is more than Knapsack capacity W, then
        // this item cannot be included in the optimal solution
        if (weight[n - 1] > totalWeight)
            return knapSack(totalWeight, weight, value, n - 1);

            // Return the maximum of two cases:
            // (1) nth item included
            // (2) not included
        else return max(
                value[n - 1] + knapSack(totalWeight - weight[n - 1], weight, value, n - 1),
                knapSack(totalWeight, weight, value, n - 1)
        );
    }

}
